/*
 * @lc app=leetcode.cn id=121 lang=cpp
 *
 * [121] 买卖股票的最佳时机
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();     // 保存天数
        int tmpPrice; 
        int result = 0;
        vector<int> minPrice(length, 0);
        vector<int> maxPrice(length, 0);

        // 正序遍历，记录从开始的最低价格
        tmpPrice = prices[0];
        for (int i = 0; i < length; i++) {
            tmpPrice = min(tmpPrice, prices[i]);
            minPrice[i] = tmpPrice;
        }
        
        // 逆序遍历，记录从最后的最高价格
        tmpPrice = prices[length - 1];
        for (int i = length - 1; i >= 0; i--) {
            tmpPrice = max(tmpPrice, prices[i]);
            maxPrice[i] = tmpPrice;   
        }

        // 正序遍历，寻找最大差价
        for (int i = 0; i < length; i++) {
            if (maxPrice[i] - minPrice[i] > 0) {
                result = max(result, maxPrice[i] - minPrice[i]);
            }
        }

        return result;
    }
};
// @lc code=end

